Vào tháng 7 năm 2014, Avicii chia sẻ với Rolling Stone rằng anh đã làm việc trên 70 ca khúc cho album tiếp theo của mình và sẽ bao gồm sự hợp tác với Jon Bon Jovi, Billie Joe Armstrong, Chris Martin, Wyclef Jean, Serj Tankian và Matisyahu.[3] ngày 2 tháng 3 năm 2015, Avicii trình diễn trực tiếp tại Liên hoan âm nhạc Future của Úc. Nhiều bài hát bị rò rỉ trên internet từ chương trình UMF 2015 của Avicii, bao gồm "Waiting for Love", "For a Better Day", "City Lights" và "Sunset Jesus", bị rò rỉ dưới tên "Attack".[4] Một danh sách đầy đủ các bài hát có thể được tìm thấy trên trang SoundCloud của Avicii.[5]

Ngày 22 tháng 5 năm 2015, Avicii ra mắt đĩa đơn đầu tiên, "Waiting for Love". Bài hát được đồng sản xuất bởi DJ và nhà sản xuất Martin Garrix. Gần một tháng sau, Avicii thông báo thông qua Twitter rằng anh đã hoàn thành album sau hai năm làm việc.[6] Ngày 4 Tháng 8 năm 2015, Avicii công bố trên iHeartMedia Summit về đĩa đơn tiếp theo từ Stories là "For a Better Day", với ca sĩ Alex Ebert.[7] Ngày 28 tháng 8, anh phát hành hai đĩa đơn tiếp theo của mình, trong đó có "Pure Grinding".[8]